package main

import (
	. "local/algorithm/util"
)

/**
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

方法1 两链表转化为整数，然后相加计算，再转化为链表
方法2 直接相加
	左边第一位就是最低位，相加后注意是否进位，标识在下一位计算时加上
	carry 进位变量
	sum 累加变量
	current 拼接后的链表

	结束条件是l1 l2都遍历完 并且 carry只为0
*/
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Forward *ListNode
 * }
 */

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var head = &ListNode{}
	current := head
	carry := 0
	for {
		sum := carry //注意这里sum的处理

		if l1 == nil && l2 == nil && carry == 0 { //注意carray=0的情况
			break
		}

		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}

		current.Next = &ListNode{Val: sum % 10, Next: nil}
		current = current.Next
		carry = sum / 10
	}
	return head.Next
}

func main() {
	l := GenerateLinkedList([]int{2, 4, 3})
	r := GenerateLinkedList([]int{5, 6, 4})
	//l := GenerateLinkedList([]int{5})
	//r := GenerateLinkedList([]int{5})
	m := addTwoNumbers(l, r)
	PrintLinkedList(m)
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var head = &ListNode{}
	current := head
	carry := 0
	for {
		if l1 == nil && l2 == nil && carry == 0 {
			break
		}

		sum := carry
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}
		current.Next = &ListNode{Val: sum % 10}
		current = current.Next
		carry = sum / 10

	}
	return head.Next
}
